|
|
Paralelní syntaktická analýza
Holko, Maroš ; Regéciová, Dominika (oponent) ; Meduna, Alexandr (vedoucí práce)
Práca sa zaoberá štúdiom niekoľkých metód syntaktickej analýzy, obzvlášť najmä Cocke-Younger-Kasami algoritmu. Ďalej je navrhnutý spôsob paralelizácie tohto algoritmu a jeho implementácia v jazyku C++. Na dosiahnutie paralelizácie boli použité vlákna. S prácou bola vytvorená aj konzolová aplikácia, v ktorej bol implementovaný paralelný CYK algoritmus. Zároveň bolo navrhnuté a implementované rozšírenie, ktoré zisťuje všetky postupnosti použitých pravidiel v prípade, že vstupný reťazec patrí do danej gramatiky. V závere sú diskutované jeho prednosti a nedostatky.
|
|
|
Sekvenční a paralelní gramatiky: vlastnosti a aplikace
Klobučníková, Dominika ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá problematikou sekvenčných a paralelných gramatík. Obe skupiny zastrešujú veľké množstvo gramatických tried, väčšina ktorých však nemá veľké uplatnenie kvôli komplikáciám spojeným s ich spracovaním. Práca skúma niektoré takéto gramatiky, ako napríklad gramatiky s rozptýleným kontextom, multigeneratívne gramatické systémy a interaktívne L-systémy s dôrazom na ich normálne formy. Práca následne predstavuje niekoľko algoritmov využívajúcich vlastnosti týchto gramatík, ako aj ich normálnych foriem. Tieto algoritmy sú založené na algoritme Cocke-Younger-Kasami pre bezkontextové gramatiky a dokážu spracovať ľubovoľnú gramatiku v príslušnej normálnej forme. Posledná časť práce predstavuje program implementujúci navrhnuté algoritmy.
|
|
|
Obecné gramatiky: Normální formy a jejich aplikace
Klobučníková, Dominika ; Krčmář, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá problematikou obecných gramatík, normálnych foriem a ich aplikácií. Zameriava sa na kontextové gramatiky ako ich špeciálne prípady. Na základe analýzy tejto množiny bol navrhnutý algoritmus využívajúci princípy Cocke-Younger-Kasami algoritmu za účelom rozhodnutia, či zadaný reťazec je vetou jazyka definovaného kontextovou gramatikou. Výsledná aplikácia implementujúca toto riešenie je navrhnutá pre prácu s kontextovými gramatikami v Penttonenovej normálnej forme.
|
|
|
Syntaktická analýza pro ET0L systémy
Kožár, Tomáš ; Klobučníková, Dominika (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto bakalárska práca sa zaoberá zisťovaním príslušnosti reťazcov do jazykov generovaných ET0L systémami. To je dosiahnuté navrhnutím dvoch algoritmov. Prvý je modifikáciou už existujúceho algoritmu Cocke-Younger-Kasami pre syntaktickú analýzu bezkontextových gramatík v Chomského normálovej forme. Pri modifikácii museli byť zohľadnené odlišné vlastnosti ET0L systémov oproti BKG, konkrétne paralelná aplikácia pravidiel a viacero množín pravidiel. Je taktiež využitá odlišná normálová forma, nakoľko CNF je pre ET0L systémy nevyhovujúca. Druhý algoritmus je založený na princípe zhora dole a postupne generuje všetky platné slová. Výsledné algoritmy sú otestované, demonštrované a funkčné. Prínosom tejto práce sú dva nové algoritmy pre syntaktickú analýzu ET0L systémov.
|
|
|
Final Sentential Forms and Their Applications
Kožár, Tomáš ; Kövári, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
Context-free grammars are one of the most used formal models in formal language theory. They have many useful applications, but for many applications, they lack expressive power. We introduce a final language F . When a sentential form of the context-free grammar G belongs to the F , it becomes a final sentential form. By the erasion of the nonterminals from the final sentential forms, we receive a language of G finalized by F , L(G,F) . We prove that for each recursively enumerable language L , there exists context-free grammar G , such that L = L(G,F) , with F = { w#reversal(w) | w is from {0,1}*}, where reversal(w) is a reversal of w . When a regular language is used as F , no increase in generative power compared to context-free grammars is achieved. We show multiple applications of the final sentential forms in the fields of the linguistics and bioinformatics.
|
|
|
Final Sentential Forms and Their Applications
Kožár, Tomáš ; Kövári, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
Context-free grammars are one of the most used formal models in formal language theory. They have many useful applications, but for many applications, they lack expressive power. We introduce a final language F . When a sentential form of the context-free grammar G belongs to the F , it becomes a final sentential form. By the erasion of the nonterminals from the final sentential forms, we receive a language of G finalized by F , L(G,F) . We prove that for each recursively enumerable language L , there exists context-free grammar G , such that L = L(G,F) , with F = { w#reversal(w) | w is from {0,1}*}, where reversal(w) is a reversal of w . When a regular language is used as F , no increase in generative power compared to context-free grammars is achieved. We show multiple applications of the final sentential forms in the fields of the linguistics and bioinformatics.
|
|
|
Syntaktická analýza pro ET0L systémy
Kožár, Tomáš ; Klobučníková, Dominika (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto bakalárska práca sa zaoberá zisťovaním príslušnosti reťazcov do jazykov generovaných ET0L systémami. To je dosiahnuté navrhnutím dvoch algoritmov. Prvý je modifikáciou už existujúceho algoritmu Cocke-Younger-Kasami pre syntaktickú analýzu bezkontextových gramatík v Chomského normálovej forme. Pri modifikácii museli byť zohľadnené odlišné vlastnosti ET0L systémov oproti BKG, konkrétne paralelná aplikácia pravidiel a viacero množín pravidiel. Je taktiež využitá odlišná normálová forma, nakoľko CNF je pre ET0L systémy nevyhovujúca. Druhý algoritmus je založený na princípe zhora dole a postupne generuje všetky platné slová. Výsledné algoritmy sú otestované, demonštrované a funkčné. Prínosom tejto práce sú dva nové algoritmy pre syntaktickú analýzu ET0L systémov.
|
|
|
Paralelní syntaktická analýza
Holko, Maroš ; Regéciová, Dominika (oponent) ; Meduna, Alexandr (vedoucí práce)
Práca sa zaoberá štúdiom niekoľkých metód syntaktickej analýzy, obzvlášť najmä Cocke-Younger-Kasami algoritmu. Ďalej je navrhnutý spôsob paralelizácie tohto algoritmu a jeho implementácia v jazyku C++. Na dosiahnutie paralelizácie boli použité vlákna. S prácou bola vytvorená aj konzolová aplikácia, v ktorej bol implementovaný paralelný CYK algoritmus. Zároveň bolo navrhnuté a implementované rozšírenie, ktoré zisťuje všetky postupnosti použitých pravidiel v prípade, že vstupný reťazec patrí do danej gramatiky. V závere sú diskutované jeho prednosti a nedostatky.
|
|
|
Sekvenční a paralelní gramatiky: vlastnosti a aplikace
Klobučníková, Dominika ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá problematikou sekvenčných a paralelných gramatík. Obe skupiny zastrešujú veľké množstvo gramatických tried, väčšina ktorých však nemá veľké uplatnenie kvôli komplikáciám spojeným s ich spracovaním. Práca skúma niektoré takéto gramatiky, ako napríklad gramatiky s rozptýleným kontextom, multigeneratívne gramatické systémy a interaktívne L-systémy s dôrazom na ich normálne formy. Práca následne predstavuje niekoľko algoritmov využívajúcich vlastnosti týchto gramatík, ako aj ich normálnych foriem. Tieto algoritmy sú založené na algoritme Cocke-Younger-Kasami pre bezkontextové gramatiky a dokážu spracovať ľubovoľnú gramatiku v príslušnej normálnej forme. Posledná časť práce predstavuje program implementujúci navrhnuté algoritmy.
|
|
|
Obecné gramatiky: Normální formy a jejich aplikace
Klobučníková, Dominika ; Krčmář, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá problematikou obecných gramatík, normálnych foriem a ich aplikácií. Zameriava sa na kontextové gramatiky ako ich špeciálne prípady. Na základe analýzy tejto množiny bol navrhnutý algoritmus využívajúci princípy Cocke-Younger-Kasami algoritmu za účelom rozhodnutia, či zadaný reťazec je vetou jazyka definovaného kontextovou gramatikou. Výsledná aplikácia implementujúca toto riešenie je navrhnutá pre prácu s kontextovými gramatikami v Penttonenovej normálnej forme.
|
host ::
RSS.